package Leetcode.Stack;

import java.util.Stack;

/**
 * @Author: kirito
 * @Date: 2024/4/20 12:17
 * @Description:
 *
 * 去除重复字母
 * 尝试过
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的
 * 字典序
 * 最小（要求不能打乱其他字符的相对位置）。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "bcabc"
 * 输出："abc"
 * 示例 2：
 *
 * 输入：s = "cbacdcbc"
 * 输出："acdb"
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 104
 * s 由小写英文字母组成
 */

public class removeDuplicateLetters {
    public static void main(String[] args) {
        String s = "bcabc";
        System.out.println(removeDuplicateLetters2(s));
    }
    public static String removeDuplicateLetters2(String s) {
        int len = s.length();
        //因为我在对字符进行操作的时候需要判断这个字符是否已经出现过
        //如果出现过，还需要考虑他后面还存不存在，存在的话就不能删了，不存在就可以操作这个字符
        //所以需要两个数组去存他的状态
        boolean[] vis = new boolean[26]; // 创建一个布尔型数组，用于标记字符是否出现过
        int[] num = new int[26]; // 创建一个整型数组，用于统计每个字母出现的次数
        for (int i = 0; i < s.length(); i++) { // 遍历字符串s中的每个字符
            num[s.charAt(i) - 'a']++; // 字符对应的索引值加1，用于统计出现次数
        }

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i); // 获取当前字符
            //假如出现过了，是不是他的相对位置肯定就取前面的就好了，那么这个就不要放进去了，出现次数减一就好
            if (!vis[ch - 'a']) {
                while(!stack.isEmpty() && stack.peek() > ch) {
                    if (num[stack.peek() - 'a'] > 0) {
                        vis[stack.peek() - 'a'] = false;
                        stack.pop();
                    } else {
                        break;
                    }
                }
                vis[ch - 'a'] = true;
                stack.push(ch);
            }
            num[ch - 'a'] -= 1; // 当前字符的计数减1

        }
        StringBuilder stringBuffer = new StringBuilder();
        while (!stack.isEmpty()) {
            stringBuffer.append(stack.pop());
        }
        return stringBuffer.reverse().toString();
    }
    public static String removeDuplicateLetters(String s) {
        boolean[] vis = new boolean[26]; // 创建一个布尔型数组，用于标记字符是否出现过
        int[] num = new int[26]; // 创建一个整型数组，用于统计每个字母出现的次数
        for (int i = 0; i < s.length(); i++) { // 遍历字符串s中的每个字符
            num[s.charAt(i) - 'a']++; // 字符对应的索引值加1，用于统计出现次数
        }

        StringBuffer sb = new StringBuffer(); // 创建一个StringBuffer对象，用于拼接结果字符串
        for (int i = 0; i < s.length(); i++) { // 遍历字符串s中的每个字符
            char ch = s.charAt(i); // 获取当前字符
            if (!vis[ch - 'a']) { // 如果当前字符没有被标记为出现过
                while (sb.length() > 0 && sb.charAt(sb.length() - 1) > ch) { // 当栈顶字符大于当前字符时
                    if (num[sb.charAt(sb.length() - 1) - 'a'] > 0) { // 如果栈顶字符的计数大于0
                        vis[sb.charAt(sb.length() - 1) - 'a'] = false; // 将栈顶字符标记为未出现过
                        sb.deleteCharAt(sb.length() - 1); // 删除栈顶字符
                    } else {
                        break; // 如果栈顶字符的计数为0，则跳出循环
                    }
                }
                vis[ch - 'a'] = true; // 将当前字符标记为出现过
                sb.append(ch); // 将当前字符添加到结果字符串中
            }
            num[ch - 'a'] -= 1; // 当前字符的计数减1
        }
        return sb.toString(); // 返回结果字符串

    }

}
